#include<vector>
#include<unordered_map>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
 
class Solution {
    void reduceIncr(TreeNode* trees, int add) {
        if (trees == NULL) return;
        trees->val += add;
        reduceIncr(trees->left, add);
        reduceIncr(trees->right, add);
    }

    TreeNode* copy(TreeNode* tree) {
        if (tree == NULL) return tree;
        TreeNode* node = new TreeNode(tree->val);
        node->left = copy(tree->left);
        node->right = copy(tree->right);
        return node;
    }
    vector<TreeNode*> generateTrees(int n, unordered_map<int, vector<TreeNode*>>map) {
        if (n == 0) return {NULL};
        if (map.find(n) != map.end())
            return map[n];
        vector<TreeNode*>res;
        for (int i = 0; i < n; ++i) {
            auto lefts = generateTrees(i, map);
            auto rights = generateTrees(n - i - 1,map);
            for (auto left : lefts) {
                for (auto right : rights) {
                    right = copy(right);
                    reduceIncr(right, i + 1);
                    TreeNode* tree = new TreeNode(i + 1);
                    tree->left = copy(left);
                    tree->right = right;
                    res.push_back(tree);
                }
            }
        }
        map[n] = res;
        return res;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        unordered_map<int, vector<TreeNode*>>map;
        return generateTrees(n, map);
    }
};